/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-03 16:53:36
 * @LastEditors: lily
 * @LastEditTime: 2021-04-03 17:12:30
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
//  思路：原地置换法
//  如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置
//  扫描数组，遇到nums[i]!==i，nums[i] === m，交换nums[i],nums[i]
//  在交换过程中，如果有重复的数字发生，那么终止返回ture

//  复杂度：O(n)  O(1)

var findRepeatNumber = function (nums) {
    // let obj = {}
    // for (const num of nums) {
    //     if (obj[num]) {
    //         return num
    //     }
    //     obj[num] = 1
    // }
    let temp = 0
    for (let i = 0; i < nums.length; i++) {
        while (nums[i] != i) {
            if (nums[i] === nums[nums[i]]) {
                return nums[i]
            }
            temp = nums[i]
            nums[i] = nums[temp]
            nums[temp] = temp
        }
    }
    return -1
};


console.log(findRepeatNumber([2, 3, 1, 0, 2, 5, 3]));